1. Field of the Invention
The present invention is directed to a system for caching data for a pathfinding computation.
2. Description of the Related Art
The computer has revolutionized the idea of a map from an image statically depicting the location of physical features to the electronic map, which consists of geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited; for example, electronic maps could include distances between elements, driving time, lot numbers, tax information, tourist information, etc. Additionally, storing a map as a file on a computer allows for unlimited software applications to manipulate that data.
One advantage of the electronic map is to store and determine costs associated with various portions of a map. Examples of cost include time, distance, tolls paid, ease of turning, quality of scenery, etc. Thus, a traveler may wish to know how far that traveler can drive without paying more than $10 in tolls, what restaurants are within a 10 minute drive, or what gas stations are within a one mile walk. In each of these situations, the traveler desires to know where they can travel to within a given cost. A more detailed discussion of costs can be found in U.S. patent application Ser. No. 08/756,263, Using Multiple Levels Of Costs For A Pathfinding Computation, filed Nov. 25, 1996, Richard F. Poppen, now U.S. Pat. No. 5,893,081 incorporated herein by reference.
Electronic maps can also be used for pathfinding, which is a method for computing a route between an origin and a destination. An electronic map that is used for pathfinding must carry information about the connectivity of a road network, that is, information about the ways in which pieces of road do or do not connect to each other, for example, where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. For an area of any significant extent, this is a very large amount of information. An electronic map can include tens or hundreds of megabytes of data. In order to hold such vast quantities of data economically and allow a user to replace maps with updated copies easily, many current pathfinding apparatus (which includes general purpose computers with pathfinding software, automotive navigation systems or other map application equipment) use CD-ROMs to store the electronic map data.
Although CD-ROMs hold a great deal of data, accessing that data can be relatively slow. For example, a typical CD-ROM drive used for automotive pathfinding may take on the order of ⅓ of a second for each read access. If a pathfinding system had to wait ⅓ of a second every time it needed data, the time needed to compute a path would not be acceptable to a user. A user of a navigational pathfinding system stored in a car typically would demand very fast reponse times when requesting a path because a user currently driving in the car needs to know which way to turn. For these reasons, it is very important to minimize the number of disk accesses required to compute a path. It is noted that some systems may use peripheral devices other than CD-ROMs, for example, hard disks, floppy disks, solid state memory, etc. These other storage devices suffer similar access time limitations.
One attempt to minimize the number of disk accesses required to compute a path includes grouping map data into clusters, that is, grouping together on a CD-ROM (or other storage device) information about sets of road segments often used in the same path computation. For example, a number of consecutive segments of the same street, road segments that cross each other or road segments that lead to a highway may be stored in a single cluster. Note that these clusters need not be geographically based. Information about roads on two sides of a river in an area that is not close to a bridge would probably not be stored in the same cluster, since the roads would not be used in relation to each other during path calculation even though they may be quite close to each other geographically. Information about highways over a wide area are good candidates to be stored together in one cluster because a path computation typically explores the connections of highways with other highways. There are many ways to cluster data to increase performance. One example of clustering data can be found in U.S. patent application Ser. No. 08/245,690, Method for Clustering Multi-Dimensional Data, filed May 18, 1994, Poppen et al., now U.S. Pat. No. 5,706,503, incorporated herein by reference. When clustering is used with a suitable cache methodology, the time for pathfinding is saved because information needed by the pathfinding computation is often already in the cache (or main memory) having been read as part of a cluster which includes data already used.
Caching is a well-known process of saving records recently read in order to reduce the number of disk/memory accesses. One of the most well known forms of caching includes using a small memory local to a processor called a cache memory. Certain data recently used is typically stored in the cache memory, with access to the cache memory being quicker than access to main memory. In this example, the cache memory caches data between main memory and a processor.
Another example of caching is to cache data between a storage device and main memory. An alternative to using a cache memory separate from main memory is to use a portion of main memory as the cache memory. When data is read from the storage device it is typically kept in the cache memory portion (hereinafter called xe2x80x9ccachexe2x80x9d) of the main memory for a certain amount of time so that later access to that data will be quicker than accessing the storage device. The portion of the memory allocated as the cache will hold a number of records of data along with an indication of how recently each record has been used. When the program needs to read a given record, the program first looks in the cache for the record. If the record is in the cache, the program uses the information stored in the cache rather than reading the disk file again. If the record is not in the cache, and there is enough unused space in the cache to hold the record, the record is read into the cache and then used by the program. If the record is not in the cache and there is not enough unused space in the cache to hold the record, the least recently used record or records are discarded to provide sufficient room to hold the new record. A record of data could include one or more clusters of data or another suitable arrangement of data. If map data is clustered in such a way that information regarding a given road segment is often used shortly after the use of information regarding another road segment in the same cluster there will be a significant speed improvement in the pathfinding process because the number of accesses to the CD-ROM will be decreased.
The path calculation remains a lengthy process even when using a cache as described above. Every cluster used in the computation still needs to be read at least once. Since the pathfinding computation may need to read a large number of clusters at the beginning of the pathfinding computation, the user of the pathfinding apparatus still spends a significant amount of time waiting for the pathfinding apparatus to read all the data prior to a path being calculated.
Therefore, a system is needed that reduces the amount of time needed to calculate a path from an electronic map.
The present invention, roughly described, provides for a system for computing a path in a processor readable representation of a network that caches data to be used in a pathfinding process. In one embodiment, the system chooses, automatically, an origin in a processor readable representation of a network without the pathfinding computation being requested. A preliminary pathfinding exploration is commenced and sets (or records) of data are loaded, as needed, into a processor readable storage medium. The pathfinding exploration is terminated when a predefinied condition is met. When a user requests a path to be found, the pathfinding computation proceeds with the use of the processor readable storage medium as it has been filled by the preliminary pathfinding exploration. Since the processor readable storage medium is already filled with some data, the system saves the time of loading the medium, thus reducing the processing time for the pathfinding computation.
The origin chosen by the system could be the current position of a vehicle in an electronic map, the position of the vehicle at a time in the future, a distance from the current position of the vehicle, or other area of interest. In one embodiment, the processor readable storage medium is a memory (e.g. RAM) and a portion of the memory is reserved for use as a cache memory.
There are various alternative predefined conditions for terminating the pathfinding computation. For example, the pathfinding computation can be terminated when a predetermined number of nodes have been processed, a predetermined number of sets of data have been loaded into the cache, the cache is filled to a predetermined percentage, a predetermined amount of time has elapsed or any other suitable condition for stopping. In one embodiment, after the predefined condition has been met, the system continues a second exploration which only utilizes data that has been previously loaded into the cache memory. This second pathfinding calculation effects which data is marked as recently used.
In one embodiment, after the pathfinding calculation has terminated, the system chooses, automatically, a new origin in the network without the pathfinding computation being requested. A second pathfinding calculation is calculated about the new origin and new data is loaded into the computer readable storage medium. The second pathfinding calculation is terminated when a second predefined condition is met. The second predefined condition can be the same as the first predefined condition.
One embodiment for performing the present invention includes a processor, a memory and a processor readable storage medium. The processor is programmed to choose the origin in the electronic map, commence the pathfinding exploration, load sets of data and terminate the pathfinding calculation as described above.
These and other objects and advantages of the invention will appear more clearly from the following detailed description in which the preferred embodiment of the invention has been set forth in conjunction with the drawings.